W5. Regular Limits and Stacks

Author

Manuel Mazzara

Published

February 19, 2026

1. Theory

1.1 Why Some Languages Are Not Regular

Recall that a regular language is any language that can be recognized by a finite state automaton (FSA). FSAs are powerful tools, but they have a fundamental limitation: they have only a fixed, finite amount of memory—precisely the current state. An FSA with states can “remember” only which of those states it is in, nothing more.

This limitation means FSAs cannot handle patterns that require counting to an arbitrary depth. For example:

  • : To recognize this, the machine must count a’s and then verify exactly b’s. No matter how many states the FSA has, a sufficiently large will overflow its memory.
  • : Even-length palindromes. To recognize these, the machine must remember the entire first half of the string, which can be arbitrarily long.

To prove that a language is regular, we just exhibit a working FSA. To prove that a language is not regular, however, we face a harder task: we must show that no possible FSA can recognize it. Checking every finite automaton is clearly impossible. Instead, we use a powerful theoretical tool: the Pumping Lemma.

1.2 The Pigeonhole Principle

Before stating the Pumping Lemma, we need the classic Pigeonhole Principle:

If pigeons are placed into pigeonholes and , then at least one pigeonhole must contain at least two pigeons.

pigeonhole p1 State q0 p2 State q1 p3 State q2 t1 visit 1 t1->p1 t2 visit 2 t2->p2 t3 visit 3 t3->p3 t4 visit 4 t4->p2 repeated state

Pigeonhole principle applied to automata: more visits than states force a repetition

Application to FSAs: Think of the states of an FSA as pigeonholes and the transitions traversed while reading a string as pigeons. If a string has length greater than the number of states , then while processing the string, the automaton visits more than states (counting repetitions). Since there are only distinct states, at least one state must be visited twice. That repeated state corresponds to a cycle in the automaton.

1.3 Infinite Regular Languages Must Have Cycles

Consider an infinite regular language recognized by an FSA with states. Since is infinite, there must be strings in of arbitrarily large length. When the FSA processes a sufficiently long string (one with more than symbols), it visits more than transitions. By the Pigeonhole Principle, some state must be revisited.

pumping_loop start q0 q0 start->q0 q q q0->q x q->q y qf qf q->qf z

A long accepting path must contain a loop that can be pumped

This means the automaton’s path looks like: where is the string that “loops” back to . The crucial observation: since the machine is deterministic and returns to , you can go around the loop any number of times: all lead to the same accepting state. Therefore, all these strings belong to .

1.4 The Pumping Lemma for Regular Languages
1.4.1 Formal Statement

Pumping Lemma: If is a regular language, then there exists an integer (called the pumping length or critical length) such that for every string with , there exists a decomposition satisfying:

  1. (the “pump” is non-empty)
  2. (the pump occurs early in the string)
  3. for all (pumping any number of times stays in )

The pumping length can be taken to be the number of states in the FSA recognizing .

Proof sketch: Let be an FSA with states recognizing . Take any with . While reading , the machine passes through at least states (including the start). By the Pigeonhole Principle, some state is repeated. Let the path be:

Since the first repetition must occur within the first states visited (i.e., after reading at most symbols), we have . Since is the string taking us from back to , we have . And since , pumping any number of times still returns to , after which takes us to the accepting state.

1.4.2 Necessary but Not Sufficient

The Pumping Lemma gives only a necessary condition for regularity, not a sufficient one. This means:

  • If is regular satisfies the Pumping Lemma (guaranteed)
  • If satisfies the Pumping Lemma is regular (some non-regular languages also satisfy it!)

Therefore:

  • Cannot use it to prove a language is regular
  • Can use it to prove a language is not regular (via the contrapositive)
1.4.3 The Contrapositive: Proving Non-Regularity

The contrapositive of the Pumping Lemma is:

If for every integer there exists a string with such that for every decomposition with and , there exists some with , then is not regular.

This is the tool we actually use. Think of it as a two-player game:

Player 1 (Adversary) Player 2 (You)
Picks any You choose with
Picks any split with and You find such that

You win (language is not regular) if you can always respond successfully, regardless of the adversary’s choices.

1.4.4 Standard Proof Template

Here is the standard structure for a Pumping Lemma proof:

  1. Assume for contradiction that is regular.
  2. Let be the pumping length given by the Pumping Lemma.
  3. Choose a specific word with (pick it cleverly so that any valid split must pump outside ).
  4. Consider an arbitrary valid split with and .
  5. Use the constraint to restrict where can appear.
  6. Find a specific such that .
  7. Conclude that the Pumping Lemma is violated, so is not regular.

Choosing the right word is the most creative step. A good choice forces to consist of a single type of symbol, making it easy to show that pumping breaks the language’s structure.

1.4.5 Classic Example:

Claim: is not regular.

Proof:

  1. Suppose is regular. Let be the pumping length.
  2. Choose . Note .
  3. Consider any split with and .
  4. Since and the first characters of are all ’s, the substring lies entirely within the -block. Therefore and for some , with .
  5. So .
  6. Consider : .
  7. Since , the pumped string has a’s and only b’s. Therefore .

This contradicts the Pumping Lemma. Therefore is not regular.

Three cases of the lecture analysis: The lecture also directly analyzed all possible splits without relying on , to show every possible split breaks:

  • Case 1: (only a’s) — pumping gives (more a’s than b’s)
  • Case 2: (only b’s) — pumping gives (more b’s than a’s)
  • Case 3: (mixed) — pumping gives (b’s appear in the middle)

In all cases, some pumped string is not of the form .

1.5 Pushdown Automata
1.5.1 Motivation: Going Beyond Regular Languages

The Pumping Lemma shows that FSAs are insufficient for languages like because they lack memory for counting. To recognize such languages, we need a model with more memory. The natural extension is to add a stack to the FSA, yielding a Pushdown Automaton (PDA).

The hierarchy of computational models (from weakest to strongest) looks like:

  • Combinational logic (no memory, just Boolean circuits)
  • Finite State Automata (fixed, finite memory: only the current state)
  • Pushdown Automata (unbounded stack memory: can recognize context-free languages)
  • Turing Machines (unlimited tape memory: can compute anything computable)

PDAs sit precisely in the layer above FSAs and are capable of recognizing context-free languages (CFLs), which include most programming language constructs (nested brackets, balanced parentheses, etc.).

1.5.2 What is a Stack?

A stack is a last-in, first-out (LIFO) data structure. Think of a stack of plates: you can only add or remove from the top.

stack_ops top top: c mid b top->mid pop pop top->pop low a mid->low z0 Z₀ low->z0 push push push->top

Stack behavior: push adds to the top, pop removes the most recent symbol

Operations:

  • Push: Insert a new symbol on top of the stack.
  • Pop: Remove the top symbol from the stack (also “reading” it).

The stack always has a special bottom-of-stack symbol that marks the bottom. You can check whether the stack is “empty” (contains only ).

Example — push , then , then :

Starting from an empty stack (containing only ):

  1. After pushing : stack (top to bottom)
  2. After pushing : stack
  3. After pushing : stack
  4. After popping: is removed; stack

The last symbol pushed () is the first to be popped. This is the LIFO property.

Historical note: The concept of a stack was introduced by Alan Turing in his 1946 paper on the Automatic Computing Engine (ACE). He called the operations BURY and UNBURY, and used them in the theory of subroutines.

1.5.3 Informal Description

An FSA has a read head on an input tape and a finite control unit that remembers the current state.

A Pushdown Automaton is identical, but adds a stack as external memory:

  • The finite control reads the next input symbol and the top of the stack.
  • Based on these (and the current state), it transitions to a new state and replaces the top of the stack with a string of symbols.

pda_arch input Input Tape control q input->control read a or ε next q' control->next transition stack Stack A A Z₀ stack->control top symbol next->stack replace top

PDA architecture: finite control reads input and the top of the stack, then updates both

The PDA can:

  • Push symbols onto the stack (by replacing the top with a longer string)
  • Pop the top symbol (by replacing it with )
  • Leave the stack unchanged (by replacing the top with itself)
  • Make -moves (read nothing from input, only modify the stack)
1.5.4 Formal Definition

A Pushdown Automaton is a 7-tuple:

where:

  • : finite set of states
  • : finite input alphabet
  • : finite stack alphabet (symbols that can appear on the stack)
  • : the transition function
  • : the initial state
  • : the initial stack symbol (bottom-of-stack marker)
  • : the set of accepting (final) states

Reading the transition function: A transition means: > In state , reading input symbol (or ), with on top of the stack: move to state and replace with the string .

Transitions are written on arrows as: meaning “read from input, pop from stack, push .”

  • To push below : write (replace with ; is now on top)
  • To pop : write (replace with nothing)
  • To leave stack unchanged: write
1.5.5 Moves of a PDA

Each step of a PDA depends on three things:

  1. The current state
  2. The current input symbol (or for a silent move)
  3. The top of the stack

In one move, the PDA simultaneously:

  • Changes state to some
  • Advances the input head (or stays put for -moves)
  • Replaces the top-of-stack symbol with a string

Since maps to a set of possible next configurations, PDAs are inherently nondeterministic in their general form. (A PDA is deterministic if for all and if implies .)

1.5.6 Acceptance Conditions

A PDA can accept input in two different ways:

  • Acceptance by final state: The input is fully consumed and the PDA is in an accepting state . The stack content does not matter.
  • Acceptance by empty stack: The input is fully consumed and the stack is empty (contains only or nothing). The state does not matter.

For nondeterministic PDAs, these two acceptance modes are equivalent: any language accepted by one mode can be accepted by the other with an appropriate PDA. For deterministic PDAs, however, the two modes are not equivalent.

Note: Acceptance by empty stack has a subtle restriction: the language accepted by an empty-stack PDA must be prefix-free (no string in the language is a proper prefix of another string in the language). This is because once the stack empties on reading , processing any extension becomes impossible.

1.5.7 Step-by-Step Example: PDA for

The key idea: push one for each , then pop one for each . If the stack is exactly empty when all ’s are consumed, the counts matched.

PDA construction:

States: (start), (reading ’s), (reading ’s), (accepting)

Stack alphabet: , with as the bottom marker.

Transitions:

  • : — read first ; push on top of
  • : — read subsequent ’s; push another
  • : — first ; pop one
  • : — subsequent ’s; pop one each time
  • : — end of input; if is on top (all ’s were popped), accept

Trace for input “aabb”:

Step State Remaining Input Stack (top first) Transition
1 :
2 :
3 :
4 :
5 :
6 ACCEPT

2. Definitions

  • Regular Language: A language that can be recognized by some finite state automaton. Equivalently, a language for which there exists an FSA with .
  • Pumping Lemma: A theorem stating that every regular language has a pumping length such that any word with can be split as with , , and for all .
  • Pumping Length (): The critical length in the Pumping Lemma; can be taken as the number of states in the FSA recognizing the language. Any string in the language of length must be “pumpable.”
  • Pumping (of a string): Repeating the middle portion of a decomposition any number of times. Pumping times gives .
  • Contrapositive of the Pumping Lemma: If for every there exists with such that every valid split (with , ) has some with , then is not regular.
  • Pigeonhole Principle: If objects are placed into containers, at least one container must hold more than one object.
  • Cycle (in an FSA): A path in the state diagram that starts and ends at the same state. In infinite regular languages, cycles are necessary for generating infinitely many strings.
  • Pushdown Automaton (PDA): A computational model consisting of a finite control unit, an input tape, and a stack. Formally a 7-tuple . PDAs recognize exactly the class of context-free languages.
  • Stack: A last-in, first-out (LIFO) data structure used by a PDA as its memory. Supports two operations: push (add to top) and pop (remove from top).
  • Stack Alphabet (): The finite set of symbols that may appear on the PDA’s stack. Typically includes a special bottom-of-stack marker .
  • Bottom-of-Stack Symbol (): A special symbol at the bottom of the PDA’s stack, used to detect when the stack is empty.
  • PDA Transition Function (): A function specifying the PDA’s moves. A transition means: in state , reading from input and from the stack top, move to state and replace with string .
  • -move: A transition in a PDA that reads no input symbol. The PDA changes state and modifies the stack without consuming any input character.
  • Acceptance by Final State: A PDA accepts a string if, after consuming all input, it is in a state .
  • Acceptance by Empty Stack: A PDA accepts a string if, after consuming all input, the stack is empty (contains only ). Equivalent to acceptance by final state for nondeterministic PDAs.
  • Context-Free Language (CFL): A language recognized by a pushdown automaton, or equivalently, generated by a context-free grammar. Every regular language is context-free, but not vice versa.
  • Nondeterministic PDA: A PDA where may contain multiple possible transitions (a set of size ). The PDA accepts if some sequence of choices leads to acceptance.
  • Deterministic PDA (DPDA): A PDA with at most one possible transition at each step: for all , and implies .

3. Formulas

  • Pumping Lemma (Regular Languages): For regular , such that with , split with , , and
  • Contrapositive (for proofs): is not regular if , with such that splits with and ,
  • Length after pumping:
  • Constraint on split location: forces to lie within the first symbols of
  • PDA transition notation: — read from input, pop from stack, push ; write for a silent (-)move
  • PDA formal definition: where
  • Acceptance by final state: is accepted iff for some and

4. Practice

4.1. Prove is Not Regular (Lab 5, Task 1)

Use the Pumping Lemma to prove that over is not a regular language.

(Note: denotes the reverse of string . The language consists of all even-length palindromes over .)

Click to see the solution

Key Concept: Note that is always a palindrome (since ). Choose the word : pumping the left -block yields a string with unequal -blocks, which cannot be a palindrome.

  1. Assume for contradiction that is regular. Let be the pumping length.
  2. Choose the word (take , so and ). Note .
  3. Consider an arbitrary split with and .
  4. Restrict : The first characters of are all ’s, and , so lies in the -prefix. Thus , with , , and .
  5. Pump with (remove one copy of ):
  6. Verify failure: The string has leading ’s and trailing ’s. For it to be in (an even-length palindrome), the -th character from the left must equal the -th character from the right.
    • The -th character from the left: the first characters are ’s, so position is the first . Character = .
    • The -th character from the right: the last characters are ’s. Since (as ), position from the right is still in the trailing -block. Character = .
    • Since , the string is not a palindrome, so .
  7. Conclusion: The Pumping Lemma is violated. Therefore is not regular.

Answer: is not regular.

4.2. Prove is Not Regular (Lab 5, Task 2)

Use the Pumping Lemma to prove that is not a regular language over .

Click to see the solution

Key Concept: Any string in has equal counts of ’s and ’s. Choosing forces into the -block; pumping down removes ’s without touching ’s, breaking the balance.

  1. Assume for contradiction that is regular. Let be the pumping length.
  2. Choose the word ( ’s and ’s). Note .
  3. Consider an arbitrary split with and .
  4. Restrict : Since the first characters are ’s and , lies in the -block. So with and .
  5. Pump with :
  6. Verify failure: and . Since , , so the counts are unequal. Therefore .
  7. Conclusion: The Pumping Lemma is violated. Therefore is not regular.

Answer: is not regular.

4.3. Prove is Not Regular (Lab 5, Task 3)

Use the Pumping Lemma to prove that over is not a regular language.

(Note: is the factorial of , with . So .)

Click to see the solution

Key Concept: Factorials grow faster than any linear function. Consecutive factorials satisfy , which is far larger than for large . Any pump of size cannot bridge the gap from to the next factorial , so some pumped word falls strictly between two consecutive factorials and is not in .

  1. Assume for contradiction that is regular. Let be the pumping length.
  2. Choose the word . Note for .
  3. Consider an arbitrary split with and .
  4. Determine : Let . Since , we have .
  5. Pump with :
  6. Verify failure:
    • Lower bound: (since ).
    • Upper bound: .
    • Gap to next factorial: . We need , i.e., , i.e., . Since for , this holds.
    • Therefore , so is strictly between two consecutive factorials and equals no factorial.
    • Hence .
    (For : the only split has . We use : . Since for any (as always), . )
  7. Conclusion: In all cases, some pumped word is not in . The Pumping Lemma is violated. Therefore is not regular.

Answer: is not regular.

4.4. Prove is Not Regular (Lab 5, Task 4)

Use the Pumping Lemma to prove that over is not a regular language.

Click to see the solution

Key Concept: In , the number of ’s equals the total count of ’s and ’s combined. Choose ; the constraint forces into the -block. Pumping down removes some ’s, breaking the sum constraint.

  1. Assume for contradiction that is regular. Let be the pumping length.
  2. Choose the word (take , so ). Note .
  3. Consider an arbitrary split with and .
  4. Restrict : The first characters of are all ’s, so forces to lie entirely in the -block. Thus with , and .
  5. Pump with :
  6. Verify failure: For , we’d need a’s, b’s, and the number of ’s to equal . But the actual number of ’s is (since ). Therefore .
  7. Conclusion: The Pumping Lemma is violated. Therefore is not regular.

Answer: is not regular.

4.5. Prove is Not Regular (Tutorial 5, Example 1)

Use the Pumping Lemma to prove that is not a regular language.

Click to see the solution

Key Concept: Choose the word . The constraint forces to lie entirely in the -block. Any pumping then unbalances the -to- ratio.

  1. Assume for contradiction that is regular. Let be the pumping length.
  2. Choose the word . Note , so the Pumping Lemma applies.
  3. Consider an arbitrary split with and .
  4. Restrict the position of : Since the first characters of are all ’s, and , the portion consists entirely of ’s. Therefore and for some , with , and .
  5. Pump with :
  6. Verify failure: Since , we have , so (unequal counts of ’s and ’s).
  7. Conclusion: The Pumping Lemma is violated. Therefore is not regular.

Additional analysis — all three split cases: The lecture also showed this by exhausting all possible placements of in (without assuming ):

  • (a) : pumping gives .
  • (b) : pumping gives .
  • (c) (): pumping gives . The middle contains ’s followed by ’s, so this string is not of the form . Thus not in .

In all three cases, pumping fails.

Answer: is not regular.

4.6. Prove is Not Regular (Tutorial 5, Example 2)

Use the Pumping Lemma to prove that is not a regular language over .

Click to see the solution

Key Concept: Choose . The in the center is a structural landmark: any valid string in has exactly one in the middle with equal -blocks on either side. Pumping the left -block destroys this symmetry.

  1. Assume for contradiction that is regular. Let be the pumping length.

  2. Choose the word . Note .

  3. Consider an arbitrary split with and .

  4. Restrict : Since and the first characters are all ’s, lies entirely in the leading -block. So (for some decomposition), with , .

    More precisely: , , with , .

  5. Pump with :

  6. Verify failure: . For this to be in , we’d need , but means . The left and right -blocks have different lengths, so .

  7. Conclusion: Pumping Lemma is violated. is not regular.

Answer: is not regular.

4.7. Construct a PDA for (Tutorial 5, Example 3)

Show that (which is not regular) is recognized by a pushdown automaton. Describe the PDA construction.

Click to see the solution

Key Concept: Use the stack to count ’s: push one per , then pop one per . If the stack holds exactly after all ’s are consumed, the counts matched.

pda_abn_w5 start p0 p0 start->p0 p1 p1 p0->p1 a, Z₀/AZ₀ p1->p1 a, A/AA p2 p2 p1->p2 b, A/ε p2->p2 b, A/ε p3 p3 p2->p3 ε, Z₀/Z₀

PDA for aⁿbⁿ

  1. Design the PDA:

    • States: (start), (reading ’s), (reading ’s), (accepting)
    • Stack alphabet:

  2. Transitions:

    Transition Meaning
    : First : push onto the stack
    : Each additional : push
    : First : pop one
    : Each additional : pop one
    : End of input with on top: accept

  3. Trace for :

    • : stack =
    • : stack =
    • : stack =
    • : stack =
    • : ACCEPT

  4. Correctness:

    • On input : exactly ’s are pushed, then ’s are popped. The stack returns to , and the PDA accepts.
    • On input with : either ’s remain on the stack when ’s run out, or is encountered before all ’s are read. Neither reaches on a valid -transition.

Answer: The PDA with states (accepting) and the transitions above recognizes .

4.8. Construct a PDA for (Tutorial 5, Example 4)

Show that is recognized by a pushdown automaton.

Click to see the solution

Key Concept: Push one per before the , then use the single as a pivot, and pop one per after the . The stack being empty at the end confirms equal -counts.

pda_aba start q0 q0 start->q0 q0->q0 a, Z₀/AZ₀ a, A/AA q1 q1 q0->q1 b, A/A q1->q1 a, A/ε q2 q2 q1->q2 ε, Z₀/Z₀

PDA for aⁿbaⁿ

  1. Design the PDA:

    • States: (start, reading left ’s), (pivot: saw , now reading right ’s), (accepting)
    • Stack alphabet:

  2. Transitions:

    Transition Meaning
    : First (left side): push
    : Each additional (left side): push
    : See the : do not pop yet, transition to reading right ’s
    : Each on the right side: pop one
    : All ’s matched; on top: accept

  3. Trace for :

    • : stack =
    • : stack = (stack unchanged, state changes)
    • : stack =
    • : ACCEPT

  4. Trace for :

    • : stack =
    • : stack =
    • : stack =
    • : stack =
    • : stack =
    • : ACCEPT

Answer: The PDA with states (accepting) and the transitions above recognizes .